/**
 * 二叉树基本操作
 */
package com.study.s13.binarytree;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTree {
	
	//根节点
	public Node root;
	
	/**
	 * 插入节点
	 * 从根节点开始查找一个相应的节点，这个节点将成为新插入节点的父节点
	 * 当父节点找到后，通过判断新节点的值与父节点的值的大小来决定是连接到左节点还是右节点
	 */
	public void insert(long value) {
		
		//封装节点
		Node newNode = new Node(value);
		//引用当前节点
		Node current = root;
		//引用父节点
		Node parent;
		if(root == null) {
			//第一次插入
			root = newNode;
			return;
		} else {
			while(true) {
				//父节点指向当前节点
				parent = current;
				//判断向左走还是向右走
				if(current.data > value) {
					current = current.leftChild;
					if(current == null) {
						parent.leftChild = newNode;
						return;
					}
				} else {
					current = current.rightChild;
					if(current == null) {
						parent.rightChild = newNode;
						return;
					}
				}
			}
		}
	}
	
	public void insertTwoValue(long value, String value2) {
		
		//封装节点
		Node newNode = new Node(value, value2);
		//引用当前节点
		Node current = root;
		//引用父节点
		Node parent;
		if(root == null) {
			//第一次插入
			root = newNode;
			return;
		} else {
			while(true) {
				//父节点指向当前节点
				parent = current;
				//判断向左走还是向右走
				if(current.data > value) {
					current = current.leftChild;
					if(current == null) {
						parent.leftChild = newNode;
						return;
					}
				} else {
					current = current.rightChild;
					if(current == null) {
						parent.rightChild = newNode;
						return;
					}
				}
			}
		}
	}
	//查找节点
	public Node search(long value) {
		
		//引用当前节点
		Node current = root;
		while(current.data != value) {
			if(current.data > value){
				current = current.leftChild;
			} else {
				current = current.rightChild;
			}
			//如果查找不到
			if(current == null) {
				return null;
			}
		}
		return current;
	}
	//删除节点
	public boolean delete(long value) {
		//引用当前节点
		Node current = root;
		//引用父节点
		Node parent = root;
		//是否为左节点
		boolean isLeftChild = true;
		
		while(current.data != value) {
			parent = current;
			if(current.data > value){
				current = current.leftChild;
				isLeftChild = true;
			} else {
				current = current.rightChild;
				isLeftChild = false;
			}
			//如果查找不到
			if(current == null) {
				return false;
			}
		}
		
		//进行删除
		if (current.leftChild == null && current.rightChild == null) {
			
			//删除叶子节点，该节点没有子节点
			if (current == root) {
				root = null;
			} else if (isLeftChild) {
				parent.leftChild = null;
			} else {
				parent.rightChild = null;
			}
		} else if (current.rightChild == null) {
			if (current == root) {
				root = current.leftChild;
			} else if (isLeftChild) {
				parent.leftChild = current.leftChild;
			} else {
				parent.rightChild = current.leftChild;
			}
		} else if (current.leftChild == null) {
			if (current == root) {
				root = current.rightChild;
			} else if (isLeftChild) {
				parent.leftChild = current.rightChild;
			} else {
				parent.rightChild = current.rightChild;
			}
		} else {
			Node successor = getSuccessor(current);
			if (current == root) {
				root = successor;
			} else if (isLeftChild) {
				parent.leftChild = successor;
			} else {
				parent.rightChild = successor;
			}
			successor.leftChild = current.leftChild;
		}
		return true;
	}
	
	//找到中枢后继节点
	public Node getSuccessor(Node delNode) {
		
		Node successor = delNode;
		Node successorParent = delNode;
		Node current = delNode.rightChild;
		
		while (current != null) {
			successorParent = successor;
			successor = current;
			current = current.leftChild;
		}
		if (successor != delNode.rightChild) {
			successorParent.leftChild = successor.rightChild;
			successor.rightChild = delNode.rightChild;
		}
		return successor;
	}
	
	
	/**
     * 将树转换成字符串并打印在控制台上，用L表示左孩子，R表示右孩子
     */
    public void print() {
        List<Node> tree = locateNodes();
        int size = tree.size(); //
        int deepth = 0;
        // 获取树的深度
        while ((size >>= 1) > 0) {
            deepth++;
        }
        deepth++;
        Iterator<Node> iterator = tree.iterator();
        int maxPosition = 1;
        for (int floor = 1; floor <= deepth; floor++) { // 层数，从1开始
            maxPosition = 1 << (floor - 1);
            printBlank((1 << (deepth - floor)) - 1);
            for (int position = 0; position < maxPosition; position++) {
                if (iterator.hasNext()) {
                	Node node = iterator.next();
                    if (node != null) {
                        System.out.print(node.data);
                    } else {
                        System.out.print(" ");
                    }
                    printBlank((1 << (deepth - floor + 1)) - 1);
                }
            }
            System.out.println();
        }
    }
 
    /**
     * 将二叉树用空节点补充成完全二叉树，并以水平遍历形式返回
     */
    private List<Node> locateNodes() {
        Queue<Node> queue = new LinkedList<Node>();
        List<Node> tree = new LinkedList<Node>(); // 把树补充成完全二叉树，放在这个链表中
        //queue.add(this);
        queue.add(root);
        Node empty = null;
        int nodeCount = 1; // 队列中非空节点数
        while (queue.size() > 0 && nodeCount > 0) {
        	Node node = queue.remove();
            if (node != null) {
                nodeCount--;
                tree.add(node);
                Node left = node.leftChild;
                Node right = node.rightChild;
                if (left == null) {
                    queue.add(empty);
                } else {
                    queue.add(left);
                    if (left != null) {
                        nodeCount++;
                    }
                }
                if (right == null) {
                    queue.add(empty);
                } else {
                	queue.add(right);
                    if (right != null) {
                    	nodeCount++;
                    }
                }
            } else {
            	tree.add(empty);
                queue.add(empty);
                queue.add(empty);
            }
        }
        return tree;
	}
    
	private void printBlank(int length) {
    	while (length-- > 0) {
        	System.out.print(" ");
        }
	}
}
